package randomthoughts.dp;

/**
 * @author tongchen
 * @create 2023-04-16 20:28
 */
public class CompleteBag {
    public static void main(String[] args) {

    }
    public static int completeBag(int[]weight,int[]value,int maxSize){
        //创建dp数组
        int[]dp=new int[maxSize+1];
        //由于完全背包后面的值是同情况下前面的值推导出来的，所以对于初始化，第一列中是背包容量为0的情况下。所有值都是0
        //进行遍历
        //先遍历物品
        for(int i=0;i< weight.length;++i){
            for(int j=weight[i];i<=maxSize;++j){
                dp[j]=Math.max(dp[j],dp[j-weight[i]]+value[i]);
            }
        }
        return dp[maxSize];
    }
    //先遍历容量
    public static int completeBag1(int[]weight,int[]value,int maxSize){
        int[]dp=new int[maxSize+1];
        for (int i = 1; i <=maxSize ; i++) {
            for (int j = 0; j < weight.length ; j++) {
                if(i>=weight[j]){
                    dp[i]=Math.max(dp[i],dp[i-weight[j]]+value[j]);
                }
            }
        }
        return dp[maxSize];
    }

}
